package leetcode.dp;

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * leetCode 416
 * Partition to 2 Equal Sum Subsets
 * 划分为2个相等的子集
 * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 * 思路：01背包问题，在DP上是自底向上解决，此时dp数组可以是个一维的，下标即为f(i ,c) = f(i - 1, c) && f(i - 1, c - n[i])中的i

 */
public class Dp416 {

    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        //利用hasNextXXX()判断是否还有下一输入项
        while (sc.hasNext()) {
            //利用nextXXX()方法输出内容
            String str = sc.next();
            List<Integer> input = Arrays.stream(str.split(",")).map(i -> { return Integer.parseInt(i); }).collect(Collectors.toList());
            System.out.println(Arrays.toString(input.toArray()));
            Integer [] nums = input.toArray(new Integer[input.size()]);
            new Dp416().canPartition(nums);
        }
    }

    public boolean canPartition(Integer[] nums) {
        int sum = 0;
        for(int i = 0 ; i< nums.length;i++) sum += nums[i];
        if(sum%2 != 0 || sum <= 0) return false;
        // dp[i]表示sum/2为i时能否被分割
        boolean [] dp = new boolean[sum/2 + 1];
        // 第一位就为sum/2时一定能分
        for(int i = 0;i <= sum/2 ;i ++){
            dp[i] = (nums[0] == i);
        }
        for(int i = 1;i < nums.length ; i ++){
            for(int j = sum/2;j >= nums[i] ; j --){
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[sum/2];
    }
}
